package com.zhupf.binarySearch;

/**
 * @author zhupf
 * @date 2024年01月17日 16:03
 * @Description
 *  33. 搜索旋转排序数组
 * 将数组一分为二，其中一定有一个是有序的，另一个可能是有序，也能是部分有序。
 * 此时有序部分用二分法查找。无序部分再一分为二，其中一个一定有序，另一个可能有序，可能无序。就这样循环.
 */
public class Search {

    public static void main(String[] args) {
        int[] nums = {5,1,3};
        search(nums,5);
    }



    public static int search(int[] nums, int target) {
        int left = 0;
        int right = nums.length - 1;
        while (left <= right) {
            int mid = left + (right - left) / 2;
            if (nums[mid] == target) {
                return mid;
            } else if ( left < mid && nums[left] <= nums[mid-1]) {
                if(target <= nums[mid-1] && target >= nums[left]){
                    right = mid-1;
                }else {
                    left = mid +1;
                }
            } else {
                if(right>mid && target >= nums[mid+1] && target <= nums[right]){
                    left =mid+1;
                }else {
                    right = mid -1;
                }

            }
        }
        return -1;
    }
}
